package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.*;

/**
 * 描述：
 * <p>
 * 如果数据不重复 则直接回溯 不用去重
 * 如果数据重复 直接回溯会导致 相同的值回溯多次 得到多个重复的结果 这时候就要保证 如果有重复的值则每次回溯只使用最左边的那个值 进行回溯 如果最左边的已经被用了 再往右移一位
 * 所以条件里面的 !listIndex.contains(i - 1)指的是左边的值与自身一样 且左边的值还没用的话 优先使用左边的值
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-10 09:27
 */
public class AD46全排列 {


    public static void main(String[] args) {
        int[] nums = {3,3,0,3};
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        //使用数组 值传递的时候不会被改动 不需要每次都new 一个新对象
        boolean[] booleans = new boolean[nums.length];
        permute2(nums, new ArrayList<>(), booleans, lists);
        System.out.println(lists);
    }


    //回溯2
    public static void permute2(int[] nums, List<Integer> listIndex, boolean[] booleans, List<List<Integer>> lists) {
        if (listIndex.size() == nums.length) {
            lists.add(new ArrayList<>(listIndex));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //如果值已回溯则跳过
            if (booleans[i]) {
                continue;
            }
            //如果有相同的值已回溯则跳过
            if (i - 1 >= 0
                    && !booleans[i - 1]
                    && nums[i] == nums[i - 1]) {
                continue;
            }
            booleans[i] = true;
            listIndex.add(nums[i]);
            permute2(nums, listIndex, booleans, lists);
            //还原
            booleans[i] = false;
            listIndex.remove(listIndex.size() - 1);
        }
    }

    //动态规划 --递归 不适用 key值可用价值不大 也许可以继续调优
    public static List<List<Integer>> permute3(int[] nums, List<Integer> indexList, Map<String, List<List<Integer>>> map) {
        List<List<Integer>> listsss = map.get(indexList);
        if (listsss != null) {
            return listsss;
        }
        List<List<Integer>> listss = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (indexList.contains(i)) {
                continue;
            }
            if (indexList.size() == nums.length - 1) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[i]);
                listss.add(list);
                map.put(indexList.toString(), listss);
                return listss;
            }
            List<Integer> list = new ArrayList<>();
            list.addAll(indexList);
            list.add(i);
            Collections.sort(list);
            List<List<Integer>> lists = permute3(nums, list, map);
            for (int j = 0; j < lists.size(); j++) {
                List<Integer> list1 = lists.get(j);
                list1.add(nums[i]);
                if (!listss.contains(list1)) {
                    listss.add(list1);
                }
            }
        }
        map.put(indexList.toString(), listss);
        return listss;
    }
}
